//
// Created by lyc on 2025/3/24.
//

/*
 * 01背包问题
 * 4种实现算法
 * 1 贪心
 * 2 DP(递归)
 * 3 DP(循环)
 * 4 回溯(递归)
 * */

#include <iostream>
#include <vector>
#include <map>
using namespace std;
#ifndef LAB2_KNAPSACK01_H
#define LAB2_KNAPSACK01_H

#endif //LAB2_KNAPSACK01_H



struct Item{
    int id;
    double value;
    double weight;
};

double knapsack01_DP_recursion(double surplusCapacity, vector<Item>::iterator it);
double knapsack01_DP_loop(int capacity, vector<Item> items);
void knapsack01_backtrack(double surplusCapacity, vector<Item>::iterator it, double currValue);
void quickSortByRatio(vector<Item>& items, int startLocation, int endLocation);
double knapsack01_greedy(double capacity, vector<Item>::iterator it, vector<Item>& items);
